/*
 * @lc app=leetcode.cn id=138 lang=javascript
 *
 * [138] 复制带随机指针的链表
 */

// @lc code=start
/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

/**
 * @param {Node} head
 * @return {Node}
 */
// 递归 回溯 + 哈希表
// 使用hash表存储节点，首先递归会把head上的节点都递归新建，然后从后往前回溯连接random
var copyRandomList = function(head, cachedNode = new Map()) {
  if (head === null) {
      return null;
  }
  if (!cachedNode.has(head)) {
      cachedNode.set(head, {val: head.val}),
      Object.assign(
        cachedNode.get(head),
        {
          next: copyRandomList(head.next, cachedNode), 
          random: copyRandomList(head.random, cachedNode)
        }
      )
  }
  return cachedNode.get(head);
}
// @lc code=end
// 遍历两边链表 使用hash进行构建
// var copyRandomList = function(head) {
//   let headRoot = head
//   let root = tail = null
//   let map = new Map()
//   while (headRoot) {
//     if (!root) {
//       root = tail = new Node(headRoot.val)
//     } else {
//       let newNode = new Node(headRoot.val)
//       tail.next = newNode
//       tail = tail.next
//     }
//     map.set(headRoot, tail)
//     headRoot = headRoot.next
//   }
//   headRoot = head
//   tail = root
//   while (headRoot) {
//     let random = map.get(headRoot.random)
//     if (random) {
//       tail.random = random
//     }
//     headRoot = headRoot.next
//     tail = tail.next
//   }
//   return root
// };

